#include<unordered_map>
using std::unordered_map;


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



class Solution {

private:
    unordered_map<long long, int> mp;
    int target;
public:
    int pathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        mp[0] = 1;
        return dfs(root, 0);
        
        

    }

    int dfs(TreeNode* root, long long prefix) {
        if (!root) return 0;
        int ans = 0;
        long long curSum = root->val + prefix;
        if (mp.find(curSum) == mp.end()) mp[curSum] = 0;
        
        if (mp.find(curSum-target) != mp.end()) ans += mp[curSum-target];
        mp[curSum]++;
        ans += dfs(root->left, curSum);
        ans += dfs(root->right, curSum);
        mp[curSum]--;
        return ans;
    }
    


    
};